#include <iostream>
#include <queue>
#include <string>
#define LL long long
using namespace std;

const int kMaxN = 4e5 + 10;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  for (cin >> T; T; T--) {
    int n;
    string s;
    deque<int> deq0, deq1;
    long long ans = 0;

    cin >> n >> s;
    s = '1' + s;
    for (int i = 1; i <= n; i++) {
      if (s[i] == '0') {
        deq0.emplace_back(i);
      } else {
        deq1.emplace_back(i);
      }
    }
    while (!deq0.empty() || !deq1.empty()) {
      for (; !deq0.empty() && !deq1.empty() && deq0.back() > deq1.back(); deq0.pop_back()) {
        ans += deq0.back();
      }
      if (!deq0.empty()) {
        ans += deq0.back();
        deq0.pop_back();
        if (!deq1.empty()) {
          deq1.pop_back();
        }
      } else if (!deq1.empty()) {
        ans += deq1.front();
        deq1.pop_front();
        if (!deq1.empty()) {
          deq1.pop_back();
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}